A computing system typically includes a central processing unit (CPU) (also referred to as a processor) and supporting hardware necessary to store, retrieve, and transfer information, such as communications buses and memory. The computing system may also include hardware for external communications, such as input/output controllers or storage controllers, and devices attached thereto such as keyboards, monitors, tape drives, disk drives, communication lines coupled to a network, etc. The CPU may execute instructions of a computer program to direct operation of other system components.
Computing systems typically include storage devices in communication with the processor for storing data. Storage devices used for storing mass data generally have relatively long latency time to access data stored thereon. If a processor were to access data directly from such a mass storage device every time it performed an operation, it would spend nearly all of its time waiting for the storage device to return the data, and its throughput would be very low. As a result, computer systems typically store data in a hierarchy of memory or storage devices, each succeeding level having faster access, but storing less data. At the highest level is the mass storage unit or units, which store all the data on relatively slow devices. Moving down the hierarchy is a main memory, which is generally semiconductor memory. Main memory has a much smaller data capacity than the storage units, but a much faster access. Lower still are caches, which may be at a single level, or multiple levels (level 1 being the lowest), of the hierarchy. Caches are typically also semiconductor memory, but are faster than main memory, and again have a smaller data capacity.
Due to the fixed size of a cache, it generally must remove or evict data to make room for newly received data. Often, the data selected for removal will be referenced again soon afterwards. In particular, where the cache is designed using associativity sets, another cache line in the same associativity set must be selected for removal. If a particular associativity set contains frequently referenced cache lines (referred to as a “hot” associativity set), it is likely that the evicted cache line will be needed again soon.
Some multi-level caches use a “victim cache,” which is typically an intermediate cache level that receives all evicted cache lines from a cache level immediately above it in the cache hierarchy. The victim cache may buffer evicted cache lines from a cache level before final eviction to memory. The victim cache may hold the buffered cache lines for a certain amount of time, allowing the cache system to bring the evicted cache lines back in before their final eviction.